¿Qué es el procesamiento de transacciones ejemplo? ¿Qué es el sistema de procesamiento de transacciones? ¿Qué es un proceso transaccional? ¿Dónde se utiliza el sistema de procesamiento de transacciones?

Se llama transacción a una colección de operaciones que forman una única unidad lógica de trabajo. Es una unidad de la ejecución de un programa que accede y posiblemente actualiza varios elementos de datos A nivel hardware, transcurren en diferentes tiempos, pero un sistema de base de datos debe asegurar que la ejecución de las transacciones se realice adecuadamente a pesar de la existencia de fallos (o se ejecuta la transacción completa o no se ejecuta en absoluto).

La meta de las transacciones es asegurar que todos los objetos gestionados por un servidor permanecen en un estado consistente cuando dichos objetos son accedidos por múltiples transacciones y en presencia de caídas del servidor.

Para asegurar la integridad de los datos se necesita que el sistema de base de datos mantenga las siguientes propiedades de las transacciones, denominadas propiedades ACID, acrónimo que se obtiene de las iniciales de cada una de las propiedades en inglés:

• Atomicidad (Atomicity): O bien todas las operaciones de la transacción se realizan adecuadamente en la base de datos o ninguna de ellas. Un sistema puede en algún momento alcanzar un estado inconsistente, pero hay que asegurarse de que estas inconsistencias no sean visibles: la idea es sustituir un estado inconsistente por otro consistente. De este modo, si la transacción no empieza nunca o se garantiza que se complete, un estado inconsistente no será visible excepto durante la ejecución de la transacción. Ésta es la razón de que aparezca el requisito de atomicidad. Si se proporciona esta propiedad, o todas las acciones de la transacción se ven reflejadas en la base de datos, o ninguna de ellas. El sistema de base de datos mantiene los valores antiguos (en disco) de aquellos datos sobre los que una transacción realiza una escritura y, si la transacción no completa su ejecución, los valores antiguos se recuperan para que parezca que la transacción no se ha ejecutado.
• Consistencia (Consistency)/integridad: La ejecución aislada de la transacción (es decir, sin otra transacción que se ejecute concurrentemente) conserva la consistencia de la base de datos. Cada vez que se consulta a la base de datos, la misma se encuentra en un estado consistente, es decir, o en el estado anterior a la ejecución de la transacción o en el estado posterior (si se ejecutó correctamente). Es decir, debe asegurar que no se rompe ninguna regla de integridad llevando a la bbdd de un estado válido a otro.
• Aislamiento (Isolation): sobre la base de datos pueden estar ejecutándose varias transacciones en paralelo (o de forma concurrente), es decir, se ejecutan antes de que finalice otra transacción en ejecución. El resultado en la base de datos debería ser el mismo que si se hubiesen ejecutado secuencialmente (esto significa que el resultado debe ser secuencial), en cualquier orden, una transacción no puede afectar o interferir con otras.
• Durabilidad (Durability): una vez que el SGBD informó que la transacción se ejecutó correctamente, los resultados son recuperables a nivel de disco. Los cambios realizados en la base de datos permanecen, incluso si hay fallos en el sistema. Se puede garantizar la durabilidad si se asegura que:
1. Las modificaciones realizadas por la transacción se guardan en disco antes de que finalice la transacción.
2. La información de las modificaciones realizadas por la transacción guardada en disco es suficiente para permitir a la base de datos reconstruir dichas modificaciones cuando el sistema se reinicie después del fallo.

Una alternativa a ACID es BASE, que resulta ser el acrónimo de los siguientes conceptos:

• BASICALLY AVAILABLE: implica la disponibilidad de los datos como prioridad.
• SOFT STATE: la consistencia de datos se delega a una gestión externa al motor de bbdd. Es decir, prioriza la propagación de datos delegando el control de inconsistencias a elementos externos.
• EVENTUAL CONSISTENCY: intenta lograr la convergencia hacia un estado consistente. Es decir, asume que inconsistencias temporales progresan a un estado final estable.

Para poner en relación ambos modelos se debe hacer referencia al teorema CAP. Este teorema sostiene que para un sistema computacional distribuido es imposible ofrecer simultáneamente las siguientes tres garantías:

• Consistencia (Consistency): todos los nodos ven los mismos datos al mismo tiempo.
• Disponibilidad (Availability): garantiza que cada petición recibe una respuesta acerca de si tuvo éxito o no.
• Tolerancia a la partición (Partition): el sistema continúa funcionando a pesar de la pérdida de mensajes.

Por un lado los sistemas ACID priman la consistencia y aportan una robustez a costa del rendimiento y operatividad a medida que el volumen de datos aumenta. En contraposición el principio BASE fomenta el rendimiento, la disponibilidad y la escalabilidad.

Estados de las transacciones

Una transacción, a lo largo de su ejecución, atraviesa diferentes estados.

Toda transacción está activa al momento de iniciarse. Una vez ejecutadas todas las operaciones la transacción pasa de estar activa a estar parcialmente comprometida: en este punto la transacción ha terminado su ejecución, pero es posible que aún tenga que ser abortada, puesto que los datos actuales pueden estar todavía en la memoria principal y puede producirse un fallo en el hardware antes de que se complete con éxito. El sistema de base de datos escribe en disco la información suficiente para que, incluso al producirse un fallo, puedan reproducirse los cambios hechos por la transacción al reiniciar el sistema tras el fallo. Cuando se termina de escribir esta información, la transacción pasa al estado comprometido.

Una transacción llega al estado fallido después de que el sistema determine que dicha transacción no puede continuar su ejecución normal (por ejemplo, a causa de errores de hardware o lógicos). Una transacción de este tipo se debe retroceder, es decir, se deshacen todos los cambios que se hubieran realizado en la base de datos para devolverla a un estado consistente. Después pasa al estado abortada, lo que significa que la base de datos queda como si nunca se hubiese ejecutado la transacción. En este punto, el sistema tiene dos opciones:

1. Reiniciar la transacción: esto se hace sólo si la transacción se ha abortado a causa de algún error hardware o software que no lo haya provocado la lógica interna de la transacción. Una transacción reiniciada se considera una nueva transacción.
2. Cancelar la transacción: normalmente se hace esto si hay algún error interno lógico que sólo se puede corregir escribiendo de nuevo el programa de aplicación, o debido a una entrada incorrecta o a que no se han encontrado los datos deseados en la base de datos.

Recuperación ante fallos

El sistema de bases de datos debe realizar con anticipación acciones que garanticen que las propiedades de atomicidad y durabilidad de las transacciones se preserven a pesar de la ocurrencia de fallos. Una parte integral de un sistema de bases de datos es un esquema de recuperación, el cual es responsable de la restauración de la base de datos al estado consistente previo al fallo. El esquema de recuperación también debe proporcionar alta disponibilidad; esto es, debe minimizar el tiempo durante el que la base de datos no se puede usar después de un fallo.

La idea de la recuperación ante fallos es prepararse para la posibilidad de que una transacción no se complete por un fallo y evitar así que la base de datos quede en un estado inconsistente.

Estructura y tipos de almacenamiento

Los diferentes elementos que componen una base de datos pueden ser almacenados y se puede acceder a ellos en diferentes medios de almacenamiento:

Volátil

No volátil

Estable

• Memoria principal/caché.
• Acceso rápido.
• No sobrevive a las caídas de sistema.
• Memoria secundaria
• Acceso más lento
• Sobrevive a las caídas de sistema.
• Se implementa a través de soluciones como los sistemas RAID o los Sistemas de Copia de Seguridad Remota.
• La información “nunca” se pierde.

Clasificación de los fallos

Para determinar el medio por el que el sistema debe recuperarse de los fallos, es necesario identificar los modos de fallo de los dispositivos de almacenamiento:

• Fallo en la transacción: puede deberse a un error lógico o a un error del sistema:
• Error lógico: La transacción no puede continuar con su ejecución normal a causa de alguna condición interna.
• Error de sistema: El sistema se encuentra en un estado no deseado como consecuencia del cual una transacción no puede continuar con su ejecución normal. La transacción, sin embargo, se puede volver a ejecutar más tarde.

El fallo en una transacción no debería afectar al resto de transacciones que se estén ejecutando.

• Fallo del sistema: Un mal funcionamiento del hardware o un error en el software de la base de datos o del sistema operativo causa la pérdida del contenido de la memoria volátil y aborta el procesamiento de una transacción. El contenido de la memoria no volátil permanece intacto y no se corrompe. Estos fallos afectan a todas las transacciones que se estén ejecutando.
• Fallo de disco: Un bloque del disco pierde su contenido como resultado de una colisión de la cabeza lectora, o de un fallo durante una operación de transferencia de datos. Implica la pérdida de los datos almacenados, por ello es más grave que los anteriores. Las copias de los datos que se encuentran en otros discos o en archivos de seguridad en medios de almacenamiento secundarios se utilizan para recuperarse del fallo. Este tipo de caídas no ocurren en aquellos discos que son tolerantes a fallos (tipo de almacenamiento estable).

Técnicas de recuperación

Las técnicas de recuperación ante fallos que se pueden implementar en una base de datos son:

Recuperación ante fallos con pérdida de memoria volátil

Registro histórico

SELECT * FROM fn_dblog(null,null) t

El registro histórico es una secuencia de registros que mantiene un rastro de las actualizaciones realizadas a la base de datos. Cada registro (o línea) posee valores de los datos. La solución busca, como otras técnicas de recuperación, resolver el problema de cómo guardar los cambios realizados en la base de datos y los distintos valores de los datos (no solamente los datos en sí mismos).

Un registro histórico almacena secuencialmente distintos registros, donde guarda cambios como:

• Registros de inicio de transacción: iniciada>
• Registros de compromiso de una transacción: comprometida>
• Registros de aborto de una transacción: abortada>
• Registros de actualización de una transacción: ()
• Identificador de transacción: identificador único de la transacción que realiza la operación de escritura.
• Identificador del elemento de datos: identificador único del elemento de datos que se escribe. Normalmente suele coincidir con la ubicación del elemento de datos en el disco.
• Valor anterior: valor que tenía el elemento de datos antes de la escritura.
• Valor nuevo: valor que tendrá el elemento de datos después de la escritura.

Las lecturas de datos no se registran, ya que no interesan a nivel de recuperación.

Cuando una transacción realiza una escritura es fundamental que se cree el registro del registro histórico correspondiente a esa escritura antes de modificar la base de datos. Una vez que el registro del registro histórico existe, se puede realizar la salida de la modificación a la base de datos si se desea. Además, es posible deshacer una modificación que ya haya salido a la base de datos. Se deshará utilizando el campo de valor anterior de los registros del registro histórico.

El registro histórico se guarda en el almacenamiento estable para que sus registros sean útiles para recuperarse frente a errores del disco o del sistema. Una vez escritos, la transacción ya se vuelve recuperable. Se lo trabaja en la memoria principal. Las líneas del registro histórico de una transacción se guardan en disco antes de que se comience a trabajar con los bloques en el disco que contienen los datos (en otras palabras, antes de que inicie la transacción).

Con esta técnica se trabaja con dos espacios en la memoria intermedia: uno para trabajar los bloques de datos y otros para guardar en disco los bloques correspondientes al registro histórico. Estos últimos se guardan antes de trabajar con los datos de la base porque son los que van a permitir la recuperación en caso de necesitarla.

Existen dos maneras de trabajar con el registro histórico, que se diferencian respecto al momento en el que se van a actualizar los datos:

Técnica

Actualización diferida

Actualización inmediata

Definición

Garantiza la atomicidad de las transacciones mediante el almacenamiento de las modificaciones en el registro histórico, pero retardando la actualización en la base de datos hasta que la transacción se compromete parcialmente.

Permite realizar escrituras en la base de datos mientras la transacción aún se encuentra en estado activo.

Procedimiento de recuperación

Rehacer la transacción para todas aquellas transacciones iniciadas y comprometidas. Así, si el sistema cae después de que la transacción complete su ejecución, la información en el registro histórico se utiliza para restituir el sistema a un estado consistente anterior.

• Deshacer la transacción, para todas aquellas transacciones iniciadas y no comprometidas, usando los valores iniciales.
• Deshacer y luego rehacer la transacción para todas aquellas transacciones iniciadas y comprometidas.

Explicación

Los datos se actualizan en memoria secundaria cuando la transacción se compromete parcialmente, ya que se usarán para la ejecución de las escrituras diferidas. Si el sistema cae antes de que la transacción complete su ejecución o si la transacción se aborta, la información del registro histórico se ignora. Por eso, los registros del registro histórico, en este caso, no guardan el valor inicial del dato ya que sólo se rehace la transacción: en cualquier estado en que se encuentre la base de datos, el resultado final es consistente (los valores de los datos serán los correctos). Al sólo rehacer los cambios, la recuperación es más rápida.

Los datos se escriben en disco a medida que se ejecuta la transacción (antes de que cada operación de la transacción se inicie). Las modificaciones de datos escritas por transacciones activas se denominan modificaciones no comprometidas. En este caso sí importan los valores iniciales: se los usa para restaurar los elementos de datos modificados a los valores que tuvieran antes de comenzar la transacción. La acción de recuperación dependerá de en qué estado estaba la transacción en el momento en el que se cayó el sistema.

Problemas

En transacciones largas, la memoria intermedia puede verse sobrecargada, ya que los datos actualizados no se escribirán en disco hasta que se comprometa la transacción, quedando un gran volumen de datos en la memoria intermedia.

La recuperación es más lenta, ya que deshace las transacciones no comprometidas y deshace y rehace aquellas que quedaron comprometidas.

Es importante tener en cuenta que cualquiera de estos procedimientos de recuperación ante fallos son operaciones independientes. Esto significa que pueden ejecutarse tanto si la base de datos quedó desactualizada (ya que se pisan los viejos valores con los nuevos) como si quedó actualizada y sin importar la cantidad de veces que se ejecute (ya que los nuevos valores se pisan con esos mismos valores). Tanto si se hace varias veces como si se hace una vez o si se hace en cualquier estado de la base de datos, el estado final de la misma será un estado consistente (siempre se llega a este resultado).

La idea del registro histórico es poder reconstruir el estado consistente de la base de datos. Dado que el flujo de datos es bidireccional entre la memoria principal y la secundaria y que la memoria principal es volátil, la recuperación se hace en base a la memoria secundaria y por eso el registro histórico se guarda allí.

Punto de revisión (checkpoint)

Dado que el registro histórico guarda registros de transacciones hechas con anterioridad, es necesario saber qué transacciones deben deshacerse o rehacerse. Los puntos de revisión son registros del registro histórico que evitan tener que recorrerlo totalmente en cada recuperación y deshacer o rehacer transacciones que ya se han reflejado en la base de datos. Permiten una mayor eficiencia en la recuperación.

Cuando se produce un fallo, el esquema de recuperación examina el registro histórico para determinar la última transacción que comenzó su ejecución antes de que tuviera lugar el último punto de revisión. Para encontrar una transacción de este tipo se recorre el registro histórico hacia atrás, esto es, se empieza a buscar por el final del registro histórico hasta que se encuentra el primer punto de revisión (como se va recorriendo el registro histórico hacia atrás, el punto de revisión encontrado corresponde al último punto del registro histórico). Finalmente se evalúa en qué momento se comprometió la transacción:

Mientras se lleva a cabo un punto de revisión no se permite que ninguna transacción realice acciones de actualización, tales como escribir en un bloque de memoria intermedia o escribir un registro del registro histórico.

Registro histórico, base de datos y almacenamiento: gestión de la memoria intermedia

El coste de realizar la escritura en almacenamiento estable de un bloque es suficientemente elevado para que sea deseable escribir de una sola vez varios registros del registro histórico. Para hacer esto se escriben los registros del registro histórico en una memoria intermedia almacenada en la memoria principal en la que permanecen durante un tiempo hasta que se guardan en almacenamiento estable. Se pueden acumular varios registros del registro histórico en la memoria intermedia del registro histórico y escribir en almacenamiento estable con una sola operación. El orden de los registros del registro histórico en el almacenamiento estable debe ser exactamente el mismo orden en el que fueron escritos en la memoria intermedia del registro histórico.

Los nuevos valores de un dato podrán volcarse a disco aún si la transacción no está comprometida todavía siempre y cuando el bloque del registro histórico se haya guardado en disco primero. Eso permitirá recuperar el estado consistente de la base de datos en cualquier situación.

Los bloques de datos podrán guardarse en disco si antes se guardaron allí los bloques del registro histórico que contienen los registros con la información de los valores que se modificaron en ese bloque de datos. Eso permite no sólo recuperar el estado consistente de la base de datos, sino también deshacer dichas transacciones de ser necesario.

No hace falta guardar todo el registro histórico sino sólo aquellos registros del registro histórico que tienen los valores que se modificaron del bloque de datos que se desea llevar al disco.

Técnica de actualización diferida

Garantiza la atomicidad de las transacciones mediante el almacenamiento de las modificaciones en el registro histórico, pero retardando la actualización en la BD hasta que la transacción se compromete parcialmente.

Las páginas pasan de la memoria caché a la memoria externa bien al confirmarse la transacción o bien agrupando un cierto número de transacciones confirmadas (técnicas de agrupamiento de operaciones).

1. Guarda todos los bloques en memoria secundaria
2. Después se vuelva a disco

No necesita deshacer, solo voy a disco cuando las trix están commit

Ante un fallo: se rehacen trx comprometidas



Técnica de actualización inmediata

Las páginas son inicialmente actualizadas en caché. Tan pronto como se origina una modificación a la página dicha página se copia a la memoria externa. Permite realizar escrituras en la BD mientras la transacción aún se encuentra en estado activo.

• A medida que modifico los datos en el histórico, voy impactando en el disco
• Ante un fallo rehacer las commited, y deshacer las demás
• Es más rápido en la operatoria, el reg histórico es más largo ya que guardo la versión anterior y la recuperación es más lenta

Procedimientos de recuperación ante un fallo: -> Operaciones idempotentes

• Deshacer T0: Para Tx iniciadas y no comprometidas.
• Rehacer T0: Para Tx iniciadas y comprometidas.

Esquema de recuperación ARIES

ARIES es un algoritmo de recuperación avanzado que intenta reducir el tiempo de recuperación.

• Cada registro del registro histórico tiene un número de secuencia del registro histórico (NSR). También utiliza estos números en las páginas de la BD (NSR Página) para identificar operaciones realizadas sobre ellas.
• Tabla de páginas desfasadas o sucias (páginas actualizadas en memoria pero no en disco), para minimizar las operaciones rehacer innecesarias durante la recuperación.
• Esquema de revisión difusa.

El algoritmo ARIES consta de tres pasos:

a) Análisis. Se identifican las páginas sucias que residían en el buffer pool y el conjunto de transacciones en vuelo en el instante del fallo del sistema. También se establece el punto del log para aplicación de los siguientes pasos que coincide con el último registro de CheckPoint.

b) Redo. Se aplican las acciones para la reconstrucción hacia adelante de las transacciones que ganaron el COMMIT. Se parte del punto de inicio establecido para la recuperación en el log.

c) Undo. El log se rastrea hacia atrás desde el punto del fallo hasta el punto marcado en el log como inicio de la recuperación deshaciendo cambios en las páginas de la BDF afectadas por transacciones que no ganaron el COMMIT llegado el instante del fallo.

ARIES mantiene, además, las siguientes tablas para garantizar una recuperación eficiente:

a) Tabla de transacciones activas o en vuelo. Contiene una entrada para cada transacción activa con información del ID de la transacción, estado de la misma y puntero LSN al registro más reciente de la transacción en el log.

b) Tabla de páginas sucias. Contiene una entrada para cada página sucia en el buffer pool que incluye el ID de la página y el LSN correspondiente al registro en el log del estado actualizado inmediatamente anterior de la página.

ARIES realiza las siguientes acciones en los puntos de control del sistema:

a) Escribe un registro de inicio de checkpoint en el log.

b) Escribe un registro de fin de checkpoint en el log al que van añadidas las tablas de transacciones activas y la tabla de páginas sucias.

c) Salva el LSN del registro de inicio de checkpoint en un fichero especial de acceso rápido. Este fichero de acceso rápido se utiliza durante el procedimiento de rearranque en caliente para acceder inmediatamente al punto del log del último checkpoint.

ARIES tiene activamente una lista de estas páginas, registrando los siguientes datos en este orden:

• ID de página o bloque (NSR).
• Cuál es la última línea del registro histórico que modificó esa página o bloque.
• Cuál es la primera línea del registro histórico que modificó esa página o bloque (la que la desfasó).

Esta tabla o lista permite minimizar las operaciones de rehacer, identificando aquellas que son innecesarias durante la recuperación.

ARIES maneja otra lista: la lista de transacciones abiertas que contiene, para cada una de ellas, el ID de transacción y la última línea de la misma.

Dado que los puntos de revisión comunes se aseguran de que la memoria secundaria esté igual a la memoria principal, son muy costosos (ya que implican mucho volcado de información y detener muchas operaciones). En ARIES, cada punto de revisión en el registro histórico guarda las dos tablas mencionadas (que normalmente trabaja sólo en memoria principal), es decir, guarda la lista de páginas desfasadas y las transacciones abiertas. En función de las mismas, analiza todo lo que ocurrió desde el punto de revisión hasta que falló el sistema (a esto se lo denomina esquema de revisión difuso), luego determina qué transacciones es necesario rehacer (y las rehace) y, finalmente, cuáles hay que deshacer (y las deshace).

Ambas tablas se guardan en memoria secundaria sólo cuando hay puntos de revisión. Es decir, en el momento del crash no voy a tener los últimos datos en estas dos tablas.

https://courses.cs.washington.edu/courses/cse444/19wi/lectures/aries-example.pdf

Recuperación ante fallos con pérdida de memoria no volátil

Cuando la información se pierde de la memoria no volátil, la técnica de recuperación consiste en copias de seguridad o backup de la base de datos. La misma consiste en una copia de la base de datos, del último volcado que se hizo de la misma, lo que incluye no sólo los datos sino también el registro histórico. Ninguna transacción puede estar activa durante el procedimiento de volcado.

Existen 3 tipos de backup:

Completo (full backup)

Diferencial

Incremental

• Incluye toda la base de datos, partes del registro histórico, esquema de base de datos y estructura de archivos.
• Sirve como base para realizar los otros dos tipos de back up.

Almacena información redundante ya que los valores de datos que no se modificaron se vuelven a copiar.

• Permite respaldar los datos modificados desde el último backup completo. Por este motivo,
• requiere que haya sido realizado antes un full back up.

Lo que se guarda son las diferencias entre el último dato guardado en el back up completo. Al restaurar, se suma ese valor al diferencial para restaurar el dato.

• Realiza un respaldo de todos los datos modificados desde el último respaldo.
• Dado que almacena los cambios desde la última modificación (y no desde la última copia completa), para recuperar se requieren todas las modificaciones que se hicieron desde el último backup completo y realizar todos los cálculos para llegar al valor más reciente. Si se llegase a perder una modificación, la recuperación se vuelve imposible.
• Toma menos tiempo de ejecución que un backup diferencial, pero toma más tiempo de recuperación y es más complejo de manejar.

Control de concurrencia

Hay concurrencia cuando se permite que dos o más transacciones se ejecuten en paralelo, sin importar si están tocando los mismos datos. Permite satisfacer aquellos requerimientos de datos en paralelo: si no hubiera concurrencia, habría transacciones que tendrían que esperar para ejecutarse y eso demoraría mucho si la transacción en curso involucra demasiadas operaciones y tarda mucho en finalizar su ejecución.

Ventajas

Desventajas

• Mayor productividad.
• Mejor utilización de los recursos.
• Tiempo de espera reducido.
• Mayor probabilidad de inconsistencias.

El problema es que si las transacciones concurrentes acceden a los mismos datos se produce conflicto y hay mayor probabilidad de inconsistencia en la base de datos. La idea de los esquemas de control de concurrencia es asegurar la consistencia de la base de datos, evitando conflictos en transacciones concurrentes.

Planificaciones

Las planificaciones determinan secuencias de ejecución de las instrucciones componentes de las transacciones. Representan el orden cronológico en el que se ejecutan las instrucciones en el sistema. Una planificación para un conjunto de transacciones debe consistir en todas las instrucciones de dichas transacciones, y debe conservar el orden en que aparecen las instrucciones en cada transacción individual.

Las planificaciones pueden ser:

• Secuenciales: las transacciones se ejecutan una después de otra. Al finalizar ambas, la base de datos se encuentra en un estado consistente. Cada planificación secuencial consiste en una secuencia de instrucciones de varias transacciones, en la cual las instrucciones pertenecientes a una única transacción están juntas en dicha planificación.
• No secuenciales: permiten que una transacción comience su ejecución mientras otra está en curso, sin alterar el orden de las instrucciones de las transacciones en ejecución. La base de datos quedará en un estado consistente sólo si el resultado de su ejecución concurrente es el mismo que se daría si se hubieran ejecutado secuencialmente (en este caso se dice que son planificaciones equivalentes).

Cuando el sistema de bases de datos ejecuta concurrentemente varias transacciones, la planificación correspondiente no tiene por qué ser secuencial. Si dos transacciones se ejecutan concurrentemente, el sistema operativo puede ejecutar una transacción durante un tiempo pequeño, luego realizar un cambio de contexto, ejecutar la segunda transacción durante un tiempo, cambiar de nuevo a la primera transacción durante un tiempo y así sucesivamente. Esto es así porque el procesador sólo puede ejecutar una operación a la vez.

Conflictos de la concurrencia

No todas las ejecuciones concurrentes producen un estado correcto. Si se deja el control de la ejecución concurrente completamente al sistema operativo son posibles muchas planificaciones, incluyendo las que dejan a la base de datos en un estado inconsistente.

• Actualización pérdida: ocurre cuando dos transacciones que intentan modificar un elemento de datos leen el antiguo valor del elemento y una de ellas (T1) actualiza el dato, pero esa actualización se pierde dado que la otra transacción (T2sobrescribe ese valor sin siquiera leerlo.
• Dependencia no confirmada (lectura sucia): ocurre cuando una transacción T1 lee o actualiza un elemento de datos que ha sido actualizado por otra transacción T2 que aún no ha sido confirmada. Por lo tanto, existe la posibilidad de que se deshaga T2 y T1 haya visto un valor que ya no existe. T1 opera sobre una suposición falsa.
• Análisis inconsistente: se produce cuando una transacción T1, producto de haber leído un dato actualizado por otra transacción T2 ya confirmada, incurre en un análisis inconsistente, devolviendo un resultado erróneo.
• Lectura no repetible o difusa: se produce cuando una transacción T1 vuelve a leer un elemento de datos que ya había leído previamente pero que luego fue modificado por otra transacción T2. Así, T1 estará leyendo dos valores distintos para el mismo elemento de datos.
• Lectura fantasma: se produce cuando una transacción T1 vuelve a ejecutar una consulta que extrae una cantidad de tuplas de una relación, que ya había ejecutado anteriormente, pero que ahora devuelve una tupla adicional (fantasma) que fuera insertada por otra transacción T2 (es decir, lee un elemento de datos que antes no existía).

Es una tarea del sistema de base de datos asegurar que cualquier planificación que se ejecute lleva a la base de datos a un estado consistente. El componente que realiza esta tarea se denomina gestor de control de concurrencia.

Secuencialidad

Se puede asegurar la consistencia de la base de datos en una ejecución concurrente si se está seguro de que cualquier planificación que se ejecute tiene el mismo efecto que otra que se hubiese ejecutado sin concurrencia. Es decir, la planificación debe ser, en cierto modo, equivalente a una planificación secuencial. Cuando esto ocurre, se dice que dicha planificación es secuencial.

La secuencialidad determina una serie de reglas para controlar la concurrencia, dando lugar a dos formas diferentes de equivalencia de planificaciones:

• Secuencialidad en cuanto a conflictos: una planificación P es secuenciable en cuanto a conflictos si es equivalente en cuanto a conflictos a una planificación secuencial:
• Secuencialidad en cuanto a vistas: una planificación P es secuencial en cuanto a vistas si es equivalente en cuanto a vistas a una planificación secuencial.

Toda planificación secuencial en cuanto a conflictos es también secuencial en cuanto a vistas, pero no ocurre lo mismo a la inversa (la secuencialidad en cuanto a conflictos es más restrictiva).

Recuperabilidad

Una planificación es recuperable cuando se puede deshacer (hacer ROLLBACK) cualquiera de sus transacciones. Permite resolver los problemas que ocurren cuando una de las transacciones concurrentes falla.

La recuperabilidad se basa en determinar en qué momentos se puede comprometer una transacción y cuándo es posible hacer ROLLBACK. No se fija en la cuestión de la secuencialidad.

Las planificaciones recuperables pueden ser de dos formas:

• Con retroceso en cascada: fenómeno en el cual un fallo en una única transacción provoca una serie de retrocesos de transacciones. Esto ocurre cuando dichas transacciones en curso leen datos que ha escrito previamente la transacción que falló.
• Sin retroceso en cascada: planificaciones recuperables en las que, para todo par de transacciones Ti y Tj tales que Tj lee un elemento de datos que ha escrito previamente Ti, la operación de comprometer de Ti aparece antes que la operación de lectura de Tj. (no dejo leer hasta que commit la trx anterior)

Es deseable evitar el retroceso en cascada, ya que provoca un aumento significativo del trabajo necesario para deshacer cálculos.

La recuperabilidad busca que las transacciones puedan hacer ROLLBACK en algún momento y que eso se pueda resolver sin tener que deshacer otras transacciones involucradas. Es la forma de prevenir la lectura sucia (dependencia no confirmada) de datos.

Esquemas de control de concurrencia

Cuando se ejecutan varias transacciones concurrentemente en la base de datos, puede que deje de conservarse la propiedad de aislamiento. Es necesario que el sistema controle la interacción entre las transacciones concurrentes; dicho control se lleva a cabo a través de uno de los muchos mecanismos existentes llamado esquema de control de concurrencia.

Protocolos basados en el bloqueo

Una forma de asegurar la secuencialidad es exigir que el acceso a los elementos de datos se haga en exclusión mutua; es decir, mientras una transacción accede a un elemento de datos, ninguna otra transacción puede modificar dicho elemento. El método más habitual que se usa para implementar este requisito es permitir que una transacción acceda a un elemento de datos sólo si posee actualmente un bloqueo sobre dicho elemento.

Los protocolos de control de concurrencia basados en el bloqueo se basan en el bloqueo de datos. Para poder hacerlo, se requiere un componente adicional del SGBD que se encargue de los bloqueos, utilizándolos o negándole: es el gestor de control de concurrencia.

Existen dos tipos de bloqueos:

• Compartidos: sólo otorgan permisos para leer un dato.
• Exclusivos: sólo otorgan permisos para leer y escribir un dato.

Es necesario que toda transacción solicite un bloqueo del modo apropiado sobre un elemento de datos dependiendo de los tipos de operaciones que se vayan a realizar sobre el mismo. La petición se hace al gestor de control de concurrencia. La transacción puede realizar la operación sólo después de que el gestor de control de concurrencia conceda el bloqueo a la transacción.

Los bloqueos son compatibles unos con otros solamente en el caso en el que dos transacciones estén pidiendo un bloqueo compartido. En ese caso, ambas transacciones pueden leer el dato, pero ninguna otra transacción podrá escribir en él. Para que otra transacción pueda escribir ese dato, tiene que esperar a que el mismo se desbloquee (soltar el bloqueo). Lo mismo ocurre si una transacción tiene el bloqueo exclusivo: aquellas que pidan otro bloqueo exclusivo o compartido sobre el mismo dato deben esperar a que se suelte el bloqueo. Es importante tener en cuenta que el orden de las operaciones en una transacción nunca se altera: una transacción no puede hacer otras tareas mientras espera a que se suelte un bloqueo.

Cuando una transacción solicita un bloqueo de un modo particular sobre un elemento de datos y ninguna otra transacción posee un bloqueo sobre el mismo elemento de datos en un modo conflictivo, se puede conceder el bloqueo. Sin embargo, esto puede causar un fenómeno denominado inanición (livelock/starvation): ocurre cuando una transacción T1 tiene un bloqueo compartido sobre un dato mientras otra transacción T2 espera a que se le dé un bloqueo exclusivo sobre el mismo; paralelamente otra transacción T3 pide bloqueo compartido sobre ese dato y el gestor se lo otorga porque son bloqueos compatibles. Aunque T1 suelte el bloqueo, T2 debe seguir esperando su bloqueo exclusivo porque ahora el bloqueo compartido lo tiene T3. Si otra transacción T4 solicita un bloqueo compartido, lo obtiene y aunque T3 suelte el bloqueo, T2 sigue esperando. Como T2 nunca puede acceder al dato, se ve obligada a hacer ROLLBACK por inanición: agotó el tiempo máximo durante el cual podía esperar a que se le otorgue un bloqueo (time out). En este caso, la inanición puede resolverse agregando una condición, como puede ser denegar la solicitud de bloqueo compartido de T3 porque la petición de bloqueo exclusivo de T2 ocurrió antes.

Si no se otorga un bloqueo sobre un dato, la transacción que lo solicita debe esperar a que la transacción que posee en ese momento dicho bloqueo lo suelte. Esto es porque se apunta a la secuencialidad: la posibilidad de esperar asegura que la transacción solicitante vino después de aquella que obtuvo el bloqueo primero. Una transacción que obtuvo un bloqueo antes que otra es la que se ejecutaría primero en una planificación secuencial.

Cuanto antes se desbloquee un dato, más "rápido" va a funcionar el procesamiento de transacciones porque, en esquemas de alta concurrencia, las otras transacciones en ejecución van a esperar menos para acceder a ese dato.

Sin embargo, existen desventajas al desbloquear un dato demasiado rápido:

• Si una transacción Tx pide un bloqueo sobre un dato y luego de usarlo lo suelta, viene otra transacción Ty que lee ese mismo dato modificado y se compromete y luego Tx tiene que hacer ROLLBACK de sus operaciones, existe conflicto: Tx no podría hacer el retroceso porque Ty leyó el dato que Tx modificó y finalmente se comprometió. La planificación no es recuperable.
• Lectura no repetible: las transacciones pueden leer dos valores diferentes para el mismo dato.

Protocolo de bloqueo de 2 fases

El protocolo de bloqueo en 2 fases es un esquema de control de concurrencia que busca evitar este problema. Este protocolo exige que cada transacción realice las peticiones de bloqueo y desbloqueo de dos fases: en la fase de crecimiento la transacción debe pedir todos los bloqueos que necesita, lo que hace que aumente la cantidad de bloqueos, pero no puede liberarlos. El punto de la planificación en el cual la transacción obtiene su bloqueo final (el final de la fase de crecimiento) es el punto de bloqueo: en este punto, la transacción tiene todos los bloqueos que necesita y puede realizar todas sus operaciones. Recién ahí empieza a desbloquear todos los datos en la fase de decrecimiento y lo hace hasta que se compromete, pero en esta etapa no puede realizar más peticiones de bloqueo y, por ende, no obtendrá nuevos bloqueos.

Este esquema es secuencial en cuanto a conflictos: las planificaciones que se realicen bajo este esquema van a ser equivalentes a planificaciones secuenciales en donde aquellas transacciones que llegaron antes a su punto de bloqueo van antes en un esquema secuencial. Es decir, el orden de las transacciones va a estar dado por su punto de bloqueo. Esto soluciona el problema de la lectura no repetible. Pero puede haber deadlocks.

Sin embargo, este esquema no resuelve la posibilidad del retroceso en cascada. Por eso se trabaja con versiones menos flexibles de este protocolo.

• Estricto: la transacción debe mantener todos sus bloqueos exclusivos hasta que se comprometa. Este requisito asegura que todo dato que escribe una transacción no comprometida está bloqueado en modo exclusivo hasta que la transacción se completa, evitando que ninguna otra transacción lea el dato.
• Riguroso: la transacción debe mantener todos sus bloqueos hasta que se comprometa. En este esquema la secuencialidad se da en función al momento en el que se compromete la transacción: en una planificación secuencial se ejecuta antes una transacción que se comprometió antes bajo el esquema de 2 fases riguroso.

Estos esquemas solucionan la posibilidad de retroceso en cascada ya que ninguna transacción podrá leer un dato modificado por otra transacción hasta que esta última se comprometa.

Protocolo de bloqueo de 2 fases con intención de bloqueo

El protocolo de bloqueo de 2 fases con intención de bloqueo está basado no solamente en el bloqueo, sino también en la granularidad: divide la base de datos en zonas (tablas), éstas se subdividen en archivos (bloques/páginas) y finalmente, estos últimos se dividen en registros. Permite obtener no sólo un bloqueo sobre un elemento de datos, sino que también pueden bloquearse tablas, archivos e incluso toda la base de datos.

En función de esto, pueden identificarse bloqueos implícitos y explícitos: al pedir un bloqueo (exclusivo o compartido) sobre la base, una tabla o un archivo (bloqueo explícito) quedan implícitamente bloqueados los niveles inferiores que dependen del elemento bloqueado.

El problema es que, al momento de pedir un bloqueo, hay que verificar todos los nodos (superiores e inferiores) para chequear que no haya otros bloqueos que impidan la concesión del que se está solicitando. Para resolver esto es que se añade la intención de bloqueo: si un nodo se bloquea en modo intencional se está haciendo un bloqueo explícito en un nivel inferior del árbol. Se piden bloqueos intencionales sobre los niveles superiores al elemento que se quiere bloquear. Demuestran la intención de bloquear de forma exclusiva o compartida un nodo jerárquicamente inferior. Una transacción que quiera bloquear un nodo debe recorrer el camino en el árbol desde la raíz hasta dicho nodo. Durante el recorrido del árbol la transacción bloquea los distintos nodos en un modo intencional.

Tipo de bloqueo

Permite…

Exclusivo (X)

Leer y escribir el nodo o los nodos inferiores.

Compartido (C)

Leer los nodos inferiores.

Intencional compartido (IC)

Permite pedir bloqueo IC o C en un nodo inferior.

Intencional exclusivo (IX)

Permite pedir bloqueo IX o X en un nodo inferior.

Intencional exclusivo y compartido (IXC)

Es una combinación de bloqueo IX con bloqueo C, por lo que permite pedir bloqueo IX o X en un nodo inferior y leer los nodos inferiores. Pide bloqueos para leer varios nodos, pero escribir solamente en uno o algunos.

El protocolo de bloqueo de 2 fases con intención de bloqueo asegura la secuencialidad en cuanto a conflictos. Cada transacción Tx puede bloquear un nodo Q usando las reglas siguientes:

1. Debe observar la compatibilidad de los bloqueos, ya que en función de ellos se otorgará (o no) el bloqueo solicitado.
2. Debe bloquear la raíz del árbol en primer lugar y puede bloquearla de cualquier modo.
3. Puede bloquear un nodo Q en modo C o IC sólo si está bloqueando actualmente al padre de Q en modo IX o IC.
4. Puede bloquear un nodo Q en modo X, IXC o IX sólo si está bloqueando actualmente al padre de Q en modo IX o IXC.
5. Puede bloquear un nodo sólo si no ha desbloqueado previamente ningún nodo (porque Tx es de dos fases).
6. Puede desbloquear un nodo Q sólo si no ha bloqueado a ninguno de los hijos de Q.

En este protocolo es necesario que se adquieran los bloqueos en orden descendente (de la raíz a las hojas), y que se liberen en orden ascendente (de las hojas a la raíz).

Esquemas multiversión (marcas temporales)

Los esquemas de control de concurrencia basados en bloqueos aseguran la secuencialidad, o bien retrasando una operación, o bien abortando la transacción que realiza la operación. Esto podría evitarse si se mantuvieran en el sistema copias anteriores de cada elemento de datos.

En los esquemas de control de concurrencia multiversión, cada operación de escritura crea una nueva versión del dato. Cuando se realiza una operación de lectura, el gestor de control de concurrencia elige una de las versiones del dato que se va a leer, asegurando que dicha elección se haga de tal manera que asegure la secuencialidad. Un bloqueo impediría que una transacción lea un dato que haya sido modificado por otra hasta que esta última suelte el bloqueo. Trabajar con varias versiones permite que la transacción que necesita el dato pueda leer la versión anterior del mismo para asegurar la secuencialidad.

Ordenación por marcas temporales multiversión

En el esquema de ordenación de marcas temporales multiversión cada transacción tiene asignada una marca temporal (MT) antes de que comience su ejecución:

Las marcas temporales pueden implementarse a través de un reloj o un contador lógico. Esto permite saber el orden de cada una en el plan de ejecución, de acuerdo con la siguiente regla:

Si MTTx

Es por esto que la marca temporal implica la secuencialidad de las transacciones.

Cada versión de un dato va a tener los siguientes elementos:

• Valor del dato de esta versión.
• Marca temporal de la transacción que lo creó ((MTETx) (que no sé cuándo se hizo).
• Máxima marca temporal de transacción que lo leyó ((MTLT) (no necesariamente tiene que tratarse de Tx).

Lo que ocurra al ejecutar una transacción dependerá de la operación que intente llevar a cabo y el valor de sus marcas temporales:

Sea Qk la versión de QUE con MTEQk≤MTTx

Si Tx ejecuta la operación de leer Q

Si Tx ejecuta la operación de escribir Q

Si una transacción Tx quiere leer un dato, lee la versión de ese dato con la mayor marca temporal de creación que sea anterior a la marca temporal de Tx. Tiene que ser la MT de escritura mayor de las menores a la MT de la transacción que quiere leer.

MTE(Q)

Si una transacción Tx quiere escribir un dato y su MT es inferior a la MT de la última transacción Ty que leyó el dato, Tx tiene que hacer ROLLBACK. Al volverse a ejecutar, la MT de Tx y pasa a ser mayor a la de Ty. Es la única manera de asegurar la secuencialidad:

Si MTTx

Esta regla fuerza a que se aborte una transacción que realice una escritura “demasiado tarde”. Con más precisión, si Tx intenta escribir una versión que alguna otra transacción

haya leído, entonces no se puede permitir que dicha escritura tenga éxito.

Si MTTx

Si MTTx>MTLQk y MTTx>MTEQk Creación de una nueva versión de Qk

Ventajas

Desventajas

Bloqueo de 2 fases multiversión

El esquema de bloqueo de 2 fases multiversión funciona distinto para transacciones de sólo lectura que para transacciones de actualización (escritura). En este caso, la marca temporal siempre es un contador (no puede ser un reloj). Cada valor de un dato sólo tiene una marca temporal.

Las transacciones de actualización realizan un bloqueo de dos fases riguroso; es decir, mantienen todos los bloqueos hasta el final de la transacción. Así, se pueden secuenciar según su orden de terminación. No tienen una marca temporal asignada cuando se crean. Las transacciones de lectura sí tienen marca temporal asignada cuando se crean, al valor del contador, y para realizar las lecturas siguen el protocolo de ordenación por marcas temporales multiversión.

Si una transacción Tx de lectura quiere leer un dato, lee la mayor versión de ese mismo dato que tenga una marca temporal inferior a la de Tx, igual que en el esquema anterior. Sin embargo, lo diferente en este protocolo es que a las transacciones de actualización sólo se les asigna una marca temporal cuando se comprometen. Esto es porque el bloqueo de 2 fases que se usa es el riguroso, en donde el momento del compromiso de la transacción determina el momento en el que se ejecutarán en una planificación secuencial. Por eso, recibe como valor de marca temporal el momento en el que se compromete. Esto implica que, cuando una transacción de actualización escribe un dato, se le asigna temporalmente el valor máximo de marca temporal posible: así ninguna transacción de lectura la puede leer hasta que la transacción de actualización se comprometa (porque su valor de marca temporal nunca va a ser superior al máximo). Cuando la transacción de actualización se compromete, aumenta el valor del contador en 1 y asigna ese nuevo valor del contador a los datos que tenían ese valor de marca temporal máximo. De esta forma sólo se leerán los datos escritos por transacciones de actualización ya comprometidas, porque las nuevas transacciones de lectura tendrán un valor de marca temporal mayor que el de la última transacción de actualización comprometida.

Si una transacción de actualización Tx quiere leer un dato, siempre lee la versión más reciente del mismo porque no tiene marca temporal (existe en el tiempo cuando se compromete). Si otra transacción de actualización Ty quiere leer ese mismo dato no puede porque Tx obtuvo un bloqueo exclusivo sobre dicho dato para poder escribirlo (y aún no se comprometió). Por lo tanto, Ty tiene que esperar. Tx tendrá el bloqueo hasta que se comprometa: cuando esto pase ahí cambiará su valor de marca temporal y recién ahí Ty puede pedir su bloqueo.

Transacciones de sólo lectura

Transacciones de actualización

Tx ejecuta la operación de leer Q

Si Tx ejecuta la operación de leer Q

Si Tx ejecuta la operación de escribir Q

Se muestra el contenido de la versión más reciente de Q:

MT(Q)

Tx obtiene un bloqueo compartido sobre Q, leyendo la versión más reciente de ese dato.

Tx obtiene un bloqueo exclusivo sobre Q, creando una nueva versión de ese dato.

Al comprometerse Tx:

• Asigna MTQ= Contador + 1 a la versión creada.
• Setea Contador = Contador + 1.

Como resultado, las transacciones que comiencen después de que Tx incremente el contador observarán los valores que Tx ha actualizado, mientras que aquéllas que comiencen antes de que Tx incremente el contador observarán los valores anteriores a la actualización de Tx.

Ventajas

Desventajas

• Asegura la secuencialidad.
• Las peticiones de lectura no tienen que esperar.
• Las planificaciones son recuperables y sin cascada.
• Probabilidad de interbloqueos.

Niveles de aislamiento

Se puede ajustar el nivel de aislamiento entre las transacciones y determinar para una transacción el grado de aceptación de datos inconsistentes. A mayor grado de aislamiento, mayor precisión, pero a costa de menor concurrencia.

SQL permite que una transacción especifique si puede ser ejecutada de tal forma que se convierta en no secuencial con respecto a otras transacciones. Proporciona estas características para transacciones largas cuyos resultados no necesitan ser precisos.

Los niveles de aislamiento especificados por SQL son:

• Secuenciable: es el predeterminado.
• Lectura repetible: Sólo permite leer registros comprometidos, y además requiere que, entre dos lecturas de un registro realizadas por una transacción, no se permita que ninguna otra transacción actualice el registro. Sin embargo, la transacción puede no ser secuencial con respecto a otras transacciones.
• Lectura comprometida: Sólo permite leer registros comprometidos, pero ni siquiera requiere lecturas repetibles.
• Lectura no comprometida: Permite incluso leer registros no comprometidos. Es el nivel de consistencia más bajo que permite SQL.

Nivel de aislamiento

Lectura sucia

Lectura no repetible

Lectura fantasma

Lectura no comprometida

Sí

Sí

Sí

Lectura comprometida

No

Sí

Sí

Lectura repetible

No

No

Sí

Secuenciable

No

No

No

Interbloqueos

Existe un interbloqueo cuando existe un conjunto de transacciones tal que toda transacción del conjunto está esperando un elemento de datos bloqueado por otra transacción del conjunto. Con mayor precisión:

El único remedio a esta situación no deseada es que el sistema invoque alguna acción drástica, como hacer retroceder alguna de las transacciones involucradas en el interbloqueo. El retroceso de una transacción puede ser parcial: esto es, se puede retroceder una transacción hasta el punto donde obtuvo un bloqueo cuya liberación resuelve el interbloqueo.

Sin embargo, en general, los interbloqueos son un mal necesario asociado a los bloqueos si se quieren evitar los estados inconsistentes. Los interbloqueos son absolutamente preferibles a los estados inconsistentes, ya que se pueden tratar haciendo retroceder las transacciones, mientras que los estados inconsistentes producen problemas en el mundo real que el sistema de base de datos no puede manejar.

Existen distintos métodos para solucionar los interbloqueos:

• Prevención de interbloqueos: métodos que buscan asegurar que el sistema nunca llegue a un estado de interbloqueo.
• Temporizaciones: una transacción que haya solicitado un bloqueo espera por lo menos durante un intervalo de tiempo especificado. Si no se concede el bloqueo en ese tiempo, se dice que la transacción está fuera de tiempo y ella misma retrocede y vuelve a comenzar. Si de hecho había un interbloqueo, una o varias de las transacciones involucradas en dicho interbloqueo estarán fuera de tiempo y retrocederá, lo que permitirá continuar a las demás. Este método no previene los interbloqueos, ya que éste sucede igual: lo que ocurre es que no se lo identifica como tal y se resuelve.
• Detección y recuperación de interbloqueos: permite que el sistema llegue a un estado de interbloqueo. Periódicamente se invoca a un algoritmo que examina el estado del sistema para determinar si hay un interbloqueo. Si lo hay, entonces el sistema debe intentar recuperarse del interbloqueo, retrocediendo una o más transacciones para romper el interbloqueo.